1. Field of the Invention
The invention pertains to the field of computer graphics. More particularly, the present invention relates to a method for encoding locations of bounding boxes of drawing primitives such as triangles to be rendered on a multi-resolution display.
2. Description of the Related Art
Graphics processors typically contain at least two sections: a geometry section and a rendering section. The geometry section carries out the floating-point calculations to calculate the size and orientation of three-dimensional polygons, which are drawing primitives used in computer graphics. The most important drawing primitives used in graphics generation are triangles. The three-dimensional triangles computed by the geometry section are then projected and rendered onto the display device in two dimensions.
A technique called supersampling is used to improve the perceived quality of the display by attenuating aliasing, even though the display resolution is fixed. Supersampling can either be regular or stochastic. In regular supersampling, a number of regularly spaced samples are taken for each pixel. These samples are then re-sampled or averaged out to yield the pixel value. Stochastic supersampling, on the other hand, in some aspects more closely resembles the human eye's structure, wherein the photoreceptors of the retina are randomly and uniformly distributed, and no closer to one another than a minimum distance. In the field of computer graphics, stochastic supersampling refers to a random, uniform and independent distribution of samples for each pixel. These samples are then averaged to yield the pixel value. This effectively corresponds to creating a virtual image at high resolution and digitally down-filtering the result, to eliminate the high frequencies that are the source of aliasing. Supersampling has the practical effect of moving the Nyquist limit to higher frequencies.
To return to the human model, because the eye contains an array of non-uniformly distributed photoreceptors, it is extremely good at eliminating aliasing effects. Moreover, the photoreceptors in the foveal region of the eye, the center region, are much more tightly packed than in the peripheral region, or in the medial region between the foveal and peripheral regions. Indeed, the density of photoreceptors decreases from a maximum in the foveal region, to an intermediate distribution in the medial region, and to the lowest distribution of photoreceptors in the peripheral region.
Conventional frame buffers are memories that are organized as rectangular arrays of uniformly sampled pixel values. For every pixel on the final display device, there is a single pixel of memory storage in the frame buffer. There is thus a one to one correspondence between the 2D-memory address of a given pixel and its 2D-sample address for the mathematics of rendering.
Stochastically sampled variable resolution frame buffers, on the other hand, break the frame buffer into smaller regions whose attributes can vary dynamically. FIG. 1 shows a graphical representation of such a multi-resolution frame buffer. Reference numeral 100, generally shows a graphical representation of a multi-resolution frame buffer. The buffer is divided into three regions, each of the regions having a different sampling density. The sampling density is constant within each of the three regions. The three regions are: the foveal region 130, the medial region 120 and the peripheral region 110. The foveal region 130 is the region of highest sampling density, including 16 samples per 1 screen pixel. The foveal region is nested within the medial region, which is the region of the multi-resolution frame buffer having the next highest sampling density. The sampling density of the medial region is a constant 4 samples per 1 screen pixel. The medial region, in turn, is nested within the outermost region, the peripheral region. The sampling density of the peripheral region is 1 sample every 16 screen pixels. Thus, the multi-resolution screen buffer's structure roughly approximates the distribution of photoreceptors in the human eye.
FIG. 2 illustrates, at 200, further divisions within the multi-resolution frame buffer of FIG. 1. The peripheral region 110 and the medial regions 120 of FIG. 1 are each further divided into sub-regions labeled left, right, top and bottom. The peripheral region 110 comprises four sub-regions of the same kind, meaning four sub-regions belonging to the same region. These sub-regions are the peripheral left sub-region 213, the peripheral right sub-region 214, the peripheral top sub-region 211 and the peripheral bottom region 212. Similarly, the medial region 120 also comprises four sub-regions of the same kind: the medial left sub-region 223, the medial right sub-region 224, the medial top sub-region 221 and the medial bottom sub-region 222. The foveal region 230 is the same as the foveal region 130 of FIG. 1, and is not further broken down. Each of the regions is rectangular, allowing an easy translation from a 2D location within a sub-region to a linear address in the frame buffer memory.
FIG. 3 illustrates a multi-resolution frame buffer 300, wherein the sub-regions are further divided into bins. Bins belonging to the same region have an equal number of stochastic sample points associated therewith. The bins 330 of the foveal region 130 have a constant sample density, the bins 324 of the medial region 120 have a constant sample density and the peripheral bins 314 of the peripheral region 110 also have a constant sample density. The sampling density of the foveal region is greater than the sampling density of the medial region, which has a greater sampling density than the peripheral region. This means that the resultant image will have a greater perceived resolution at the center, the perceived resolution decreasing toward the peripheral areas of the display. Alternatively, the region of highest sampling density can be dynamically moved about the display, in synchronism with the user's eye movements, which may be tracked with an eye-tracking device. In this manner, the region of highest sampling density may be always located where the user is looking.
Triangles prior to processing are encapsulated in a bounding box. A bounding box is any box that contains a drawing primitive, such as a triangle. Such a bounding box is shown in FIG. 4 at reference numeral 402. In FIG. 4, the edges of the bounding box 402 are defined by the edges of the smallest rectangle containing the triangle 401. To reduce the accuracy requirements of the geometry and rendering sections, most computations are performed using a slightly larger box than the bounding box, instead of the full screen. Such a slightly larger box is called a bin-bounding box. The sides of a bin-bounding box correspond to the nearest integral bin-boundaries of the region having the lowest resolution. In other words, the bin-bounding box 405 shown in FIG. 4 is created by snapping the bounding box 402 to the coarsest grid, meaning the grid of next lowest resolution. As can be seen, the bin-bounding box 405 covers portions of three sub-regions. Indeed, the bin-bounding box 405 covers portions of the peripheral left sub-region, the peripheral top sub-region and the medial left sub-region.
Reference is now made to FIG. 5, which shows a bin-bounding box 505 apart from the rest of the multi-resolution frame buffer shown in FIG. 4. The bin-bounding box 505 contains three sub bounding boxes; namely, sub-box 510, sub-box 520 and sub-box 530 corresponding to the peripheral left, the peripheral top and the medial left sub-regions, respectively. The sub bounding boxes each have a constant resolution corresponding to the sub-region they occupy. Conventionally, to completely define a bin-bounding box, each of the sides of each sub bounding box had to be specified. Specification of a bin-bounding box consisted in identifying the four sides of each constituent sub bounding box, the four sides being aligned with the grid lines. As shown in FIG. 6, these four sides can be: an edge of the bin-bounding box; or any of the sub-region boundary lines: the peripheral top line PT; the peripheral bottom line PB; the peripheral right line PR; the peripheral left line PL; the medial top line MT; the medial bottom line MB; the medial right line MR; the medial left line ML; the foveal top line FT; the foveal bottom line FB; the foveal right line FR and the foveal left line FL.
Because the viewable area is divided into several regions, and because the triangles are limited in size so as not to cross more than one region boundary line, the bounding box locations may be categorized into 13 locations in the horizontal direction and 13 locations in the vertical direction, as shown in FIG. 6. The thirteen locations in the horizontal direction are:
0) to the left of the left peripheral line (PL); PA1 1) across the left peripheral line(PL); PA1 2) between the left peripheral line (PL) and the left medial (ML) line; PA1 3) across the left medial line (ML); PA1 4) between the left medial line (ML) and the left foveal line (FL); PA1 5) across the left foveal line (FL); PA1 6) between the left foveal line (FL)and the right foveal line (FR); PA1 7) across the right foveal line (FR); PA1 8) between the right foveal line (FR) and the right medial line (MR); PA1 9) across the right medial line (MR); PA1 10) between the right medial line (MR)and the right peripheral line (PR); PA1 11) across the right peripheral line (PR); and PA1 12) to the right of the right peripheral line (PR); PA1 0) below the bottom peripheral line (PB); PA1 1) across the bottom peripheral line (PB); PA1 2) between the bottom peripheral line (PB) and the bottom medial line (MB); PA1 3) across the bottom medial line (MB); PA1 4) between the bottom medial line (MB) and the bottom foveal line (FB); PA1 5) across the bottom foveal line (FB); PA1 6) between the bottom foveal line (FB) and the top foveal line (FT); PA1 7) across the top foveal line (FT); PA1 8) between the top foveal line (FT) and the top medial line (MT); PA1 9) across the top medial line (MT); PA1 10) between the top medial line (MT) and the top peripheral line (PT); PA1 11) across the top peripheral line (PT); and PA1 12) above the top peripheral line (PT); PA1 dividing a viewable area of the multi-resolution display into four quadrants; PA1 encoding only selected attributes of each of a plurality of bounding box locations within only one of the four quadrants of the multi-resolution display, the selected attributes including information regarding regions and sub-regions of different resolutions within the multi-resolution display and boundary lines therebetween; and PA1 storing the encoded selected attributes in a memory. PA1 dividing a viewable area of a multi-resolution display into four quadrants along two lines of symmetry; PA1 encoding bounding box locations only within one of the four quadrants; and PA1 setting at least one variable from which bounding box locations encoded within the one of the four quadrants of the viewable area may be extrapolated to an entire viewable area of the display. PA1 a first encoding step to encode a region of lowest resolution that is partially covered by each of the bounding boxes; PA1 a second encoding step to encode one of a number of boundary lines cutting each of the bounding boxes and a number of sub bounding boxes contained within the bounding box; PA1 a third encoding step to encode either a direction of a first cut or a direction of a sub region of lowest resolution that is partially covered by each of the bounding boxes; and PA1 a fourth encoding step to encode whether a portion of the region of lowest resolution appears on both sides of the first cut cutting through each of the bounding boxes. PA1 dividing a viewable area of the display along two perpendicular lines of symmetry to create four quadrants; PA1 encoding locations of bounding boxes of primitives to be rendered in only one of the four quadrants; PA1 setting a first and a second bit for the encoded location of each the bounding boxes, the first and second bits indicating whether each encoded bounding box location should be flipped left to right, and bottom to top, respectively, to derive the location of each of the encoded bounding boxes in each of the four quadrants from the encoded location in the one quadrant; and PA1 storing the encoded locations in a memory.
The thirteen locations in the vertical direction are the following:
With thirteen possible locations in the horizontal direction and thirteen possible locations in the vertical direction, the total number of location combinations is 13.times.13, or 169 combinations. It follows that the bin-bounding box and the sub bounding boxes locations must be defined in terms of these combinations. The solution that has been proposed thus far consists in utilizing a ROM that stores all of the combinations.
The width of a data word in such a ROM is calculated as follows. Each edge of each sub-box is encoded with 2 bits. As sub bounding boxes have four edges, 2.times.4=8 bits are needed to encode a sub bounding box. Up to three sub-boxes are potentially needed to specify a bin-bounding box which straddles three sub-regions, so 8.times.3=24 bits are needed to encode a bin-bounding box. As there are 169 possible location combinations, a 169 by 24 bit wide ROM is needed. This results in a 4056 bit ROM.
One technique that has been utilized to reduce the size of the ROM is to note that triangles that are located in groups 0 and 12, although being capable of being processed by the geometry section, cannot be rendered on the display as they would be outside of the physical boundaries of the display. Therefore, triangles that are located outside the display may safely be ignored during the rendering process. This reduces the number of different combinations of locations to 11.times.11=121. Thus, the size of the ROM can be reduced from 4056 to 121.times.24=2,904 bits.
However, a 2094 bit ROM for specifying triangle bin-bounding boxes is large, and occupies an inordinate and unacceptable silicon area on a graphics processor integrated circuit embodying such geometry and rendering sections. Moreover, such a large ROM also entails complex programming and increases the probability that errors will be introduced. Moreover, such a conventional ROM includes memory locations for bits describing each of the three sub-regions that a particular bin-bounding box may occupy. Not all triangles to be rendered, however, occupy three sub-regions. Indeed, encoding bounding boxes that do not cross sub-region boundaries, or that cross only one sub-region boundary, will result in empty spaces in the ROM that are not used. Such a ROM will not be fully populated, which is an inefficient use of the available silicon area on the integrated circuit.
What is needed, therefore, is a method for encoding bounding boxes of drawing primitives to be rendered for multi-resolution supersampled frame buffers which is more efficient than was previously available.
There is also a need for an encoding method which, by virtue of its efficiency in describing bounding box locations, simplifies programming of memories used for storing bounding box locations, and which reduces the probability that errors will be introduced therein during programming.